package leetcode.editor.cn;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

//[433]最小基因变化
public class MinimumGeneticMutation433{
public static void main(String[] args) {
   Solution solution = new MinimumGeneticMutation433().new Solution();
    int i = solution.minMutation("AACCGGTT", "AACCGGTA", new String[]{"AACCGGTA"});
    System.out.println("MinimumGeneticMutation433:main:"+i);

}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //0ms 100%
    public int minMutation(String start, String end, String[] bank) {
        if (bank == null || bank.length < 1) return -1;
        if (start == null || start.length() < 1) return -1;
        if (end == null || end.length() < 1) return -1;

        char [] map = {'A','C','G','T'};

        Set<String> bankSet = new HashSet<>();
        for (int i = 0; i < bank.length; i++) {
            bankSet.add(bank[i]);
        }
        if (!bankSet.contains(end)) return -1;//end not in bank

        Set<String> visited = new HashSet<>();
        visited.add(start);

        int step = 0;
        //bfs
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                //this floor
                String cur = queue.poll();
                char[] chars = cur.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char origin = chars[j];
                    for (int k = 0; k < map.length; k++) {
                        if (map[k] == origin)continue;
                        chars[j] = map[k];
                        String s = new String(chars);
                        if (end.equals(s) ){
                            return ++step;// not ++step false.
                        }
                        if (bankSet.contains(s) && !visited.contains(s)){
                            queue.add(s);
                            visited.add(s);
                        }
                    }
                    chars[j] = origin;
                }

            }
            step++;
        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}